package com.example.algorithm.backtracing;

import java.util.*;

/**
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * 实现词典类 WordDictionary ：
 * <p>
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 * <p>
 * 示例：
 * 输入：
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * 输出：
 * [null,null,null,null,false,true,true,true]
 * <p>
 * 解释：
 * WordDictionary wordDictionary = new WordDictionary();
 * wordDictionary.addWord("bad");
 * wordDictionary.addWord("dad");
 * wordDictionary.addWord("mad");
 * wordDictionary.search("pad"); // return False
 * wordDictionary.search("bad"); // return True
 * wordDictionary.search(".ad"); // return True
 * wordDictionary.search("b.."); // return True
 */
public class Leetcode211_WordDictionary {
    public static void main(String[] args) {
//        WordDictionary wordDictionary = new WordDictionary();
        WordDictionary2 wordDictionary = new WordDictionary2();
//        wordDictionary.addWord("bad");
//        wordDictionary.addWord("dad");
//        wordDictionary.addWord("mad");
//        wordDictionary.addWord("bac");
//        System.out.println(wordDictionary.search("pad"));
//        System.out.println(wordDictionary.search("bad"));
//        System.out.println(wordDictionary.search("bac"));
//        System.out.println(wordDictionary.search(".ad"));
//        System.out.println(wordDictionary.search("b.."));

//        wordDictionary.addWord("a");
//        wordDictionary.addWord("a");
//        wordDictionary.addWord("mad");
//        wordDictionary.addWord("bac");
//        System.out.println(wordDictionary.search("."));
//        System.out.println(wordDictionary.search("a"));
//        System.out.println(wordDictionary.search("aa"));
//        System.out.println(wordDictionary.search(".a"));
//        System.out.println(wordDictionary.search("a."));

        // ["WordDictionary","addWord","addWord","addWord","addWord","search","search","addWord","search","search","search","search","search","search"]
        // [[],["at"],["and"],["an"],["add"],["a"],[".at"],["bat"],[".at"],["an."],["a.d."],["b."],["a.d"],["."]]
        wordDictionary.addWord("at");
//        wordDictionary.addWord("and");
//        wordDictionary.addWord("an");
//        wordDictionary.addWord("add");
//        System.out.println(wordDictionary.search("a"));
//        System.out.println(wordDictionary.search(".at"));
        wordDictionary.addWord("bat");
        System.out.println(wordDictionary.search(".at"));
//        System.out.println(wordDictionary.search("at"));

//        System.out.println(wordDictionary.search("an."));
//        System.out.println(wordDictionary.search("a.d."));
//        System.out.println(wordDictionary.search("b."));
//        System.out.println(wordDictionary.search("a.d"));
//        System.out.println(wordDictionary.search(".."));


    }

    /**
     * 字典树+回溯算法
     * 添加字符串按照经典的Trie实现即可
     * 搜索时普通字符还是按照经典的Trie进行搜索
     * 当遇到'.'时遍历当前层所有非空节点并递归进行深度搜索之后的节点直到搜索到最下层或者搜索到目标字符串长度的层数
     */
    static class WordDictionary2 {
        private TrieNode root;

        public WordDictionary2() {
            root = new TrieNode();
        }

        public void addWord(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new TrieNode();
                }
                cur = cur.children[index];
            }
            cur.isWord = true;
        }

        public boolean search(String word) {
            return search(word, root);
        }

        private boolean search(String word, TrieNode root) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {

                /**
                 * 处理'.'
                 */
                if (word.charAt(i) == '.') {// 对于 . , 递归的判断所有不为空的孩子
                    for (int j = 0; j < 26; j++) {//遇到'.', 则搜索后续的字符子串是否存在
                        if (cur.children[j] != null) {
                            if (search(word.substring(i + 1), cur.children[j])) return true;// 后续的字符子串存在，返回true
                        }
                    }
                    return false;// 后续的字符子串不存在，返回false
                }

                /**
                 * 普通小写字母处理
                 */
                int index = word.charAt(i) - 'a'; // 普通小写字母,按照经典Trie查找即可
                if (cur.children[index] == null) {
                    return false;
                }
                cur = cur.children[index];
            }
            return cur.isWord;
        }
    }

    // 只有26个小写字母的TriNode
    static class TrieNode {
        private static final int CHILD_SIZE = 26;

        TrieNode[] children = new TrieNode[CHILD_SIZE];
        boolean isWord;
    }

    /**
     * 解法一:暴力法(超时)
     * HashSet存储加入的单词
     * 搜索时遍历HashSet
     * <p>
     * 解法二:HashSet + 桶排序
     * 思路:
     * 将加入的字符串按照字符串长度进行分桶
     * 搜索时只需要在对应的桶里进行搜索即可
     */
    static class WordDictionary1 {
        private Map<Integer, Set<String>> map;

        /**
         * Initialize your data structure here.
         */
        public WordDictionary1() {
            map = new HashMap<>();

        }

        public void addWord(String word) {
            map.computeIfAbsent(word.length(), key -> new HashSet<>()).add(word);

        }

        public boolean search(String word) {
            if (map.containsKey(word.length())) {
                Set<String> strs = map.get(word.length());
                Iterator<String> iterator = strs.iterator();
                while (iterator != null && iterator.hasNext()) {
                    String str = iterator.next();
                    if (equals(str, word)) return true;
                }

                return false;
            }
            return false;
        }

        private boolean equals(String str, String word) {
            for (int i = 0; i < str.length(); i++) {
                if (word.charAt(i) == '.') continue;

                if (word.charAt(i) != str.charAt(i)) return false;
            }
            return true;
        }
    }

}
